// https://leetcode.cn/problems/merge-sorted-array/

/*
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
*/
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if(m == 0){
			nums1 = nums2;
			return;
		}
		m--;
		n--;
		int total = m + n + 1;
		while(n >= 0){
			if(nums2[n] >= nums1[m]){
				nums1[total] = nums2[n];
				n--; 
			}else{
				nums1[total] = nums1[m];
				nums1[m] = INT_MIN;
				if(m > 0){
					m--;
				}
			}
			total--;
		}
    }
	
	// 先合并在排序
	void merge1(vector<int>& nums1, int m, vector<int>& nums2, int n){
		for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
	}
};

int main(){
	vector<int> nums1 = {0};
	vector<int> nums2 = {1};
	Solution so;
	so.merge(nums1,0,nums2,1);
	for(auto i:nums1){
		cout << i << ",";
	}
	cout << endl;
	
	return 0;
}